/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 *
 */
public class CopyOfPalindromePartitioningII {

	/**
	Given a string s, partition s such that every substring of the partition is a palindrome.

	Return the minimum cuts needed for a palindrome partitioning of s.

	For example, given s = "aab",
	Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
	 */
	public int minCut(String s) {
		boolean[][] palindromeDp = new boolean[s.length()][s.length()];

		int[] maxDp = new int[s.length() + 1];
		for (int i = 0; i < maxDp.length; i++) {
			maxDp[i] = s.length() - i - 1;
		}

		//Arrays.fill(maxDp, Integer.MAX_VALUE);
		for (int i = s.length() - 1; i >= 0; i--) {
			for (int j = i; j < s.length(); j++) {
				if (s.charAt(i) == s.charAt(j)
						&& (j - i < 2 || palindromeDp[i + 1][j - 1])) {
					palindromeDp[i][j] = true;
					maxDp[i] = Math.min(maxDp[i], maxDp[j + 1] + 1);
				}
			}
		}

		return maxDp[0];
	}

	public void palindrome(String s, int begin, int end, Boolean[][] dp) {
		assert (end > begin);
		if (begin == end) {
			dp[begin][end] = true;
		} else if (end - begin == 1) {
			dp[begin][end] = s.charAt(begin) == s.charAt(end);
		} else {
			if (dp[begin + 1][end - 1] == null)
				palindrome(s, begin + 1, end - 1, dp);
			dp[begin][end] = dp[begin + 1][end - 1]
					&& s.charAt(begin) == s.charAt(end);
		}
	}

	/**
	 * 
	 */
	public CopyOfPalindromePartitioningII() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		CopyOfPalindromePartitioningII ppii = new CopyOfPalindromePartitioningII();
		String s = "a";
		int min = ppii.minCut(s);

	}

}
